﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.NumSquares
{
    class MainProject
    {
        static void Main(string[] args)
        {
            //BFS ：暂时无思路
            //

            Console.WriteLine(NumSquares(15 * 4));
            Console.ReadKey();
        }

        public static int NumSquares(int n)
        {

            //DP
            //int[] dp = new int[n + 1];
            //for (int i = 1; i <= n; i++)
            //{
            //    dp[i] = i;
            //    for (int j = 1; i - j * j >= 0; j++)
            //    {
            //        dp[i] = Math.Min(dp[i], dp[i - j * j] + 1);
            //    }
            //}
            //return dp[n];

            //不完全BFS
            //Dictionary<int, int> data = new Dictionary<int, int>();
            //for (int i = 1; i <= 100; i++) data.Add(i, i * i);
            //int middle = 0;
            //int res = int.MaxValue;

            //int sup = n;
            //int reduce = n;
            //int key = (int)Math.Sqrt(sup);
            //for (int i = key; i >= 1; i--)
            //{
            //    middle = 0;
            //    sup = n;
            //    sup = sup - data[i];
            //    Console.WriteLine("Value = {0}", data[i]);
            //    middle++;
            //    while (sup != 0)
            //    {
            //        int j = (int)Math.Sqrt(sup);
            //        Console.WriteLine("Value = {0}", data[j]);
            //        sup = sup - data[j];
            //        middle++;
            //    }
            //    Console.WriteLine("****************Separator2*************");
            //    res = res > middle ? middle : res;
            //}
            //Console.WriteLine("-----------------Separator--------------------");
            //return res;


            //动态规划(666)-有点递归的意思
            //int[] dp = new int[n + 1];
            //dp[0] = 0;
            ////dp[1] = 1;
            //for (int i = 1; i <= n; i++)
            //{
            //    if (i==48)
            //    {

            //    }
            //    dp[i] = i;
            //    for (int j = 1; j * j <= i; j++)
            //    {
            //        dp[i] = Math.Min(dp[i], dp[i - j * j] + 1); 
            //    }
            //} 
            //return dp[n];



            //BFS  可以转换成树的想法
            //Dictionary<int, int> data = new Dictionary<int, int>();
            //for (int i = 1; i <= 100; i++) data.Add(i, i * i);
            //Queue<int> que = new Queue<int>();
            //HashSet<int> hash = new HashSet<int>();
            //que.Enqueue(n);
            //int sup = 0;
            //int min = int.MaxValue; ;
            //int layer = 0;
            //while (que.Count > 0)
            //{
            //    int size = que.Count;
            //    int value = 0;
            //    for (int i = 0; i < size; i++)
            //    {
            //        value = que.Dequeue();
            //        int sqr = (int)Math.Sqrt(value);
            //        for (int j = sqr; j >= 1; j--)
            //        {
            //            sup = value - data[j];
            //            //if (sup == 0) break;
            //            if (!hash.Contains(sup))
            //            {
            //                hash.Add(sup);
            //                que.Enqueue(sup);
            //            }
            //        }
            //        if (value == 0)
            //            min = Math.Min(min, layer);
            //    }
            //    layer++;
            //}
            //Console.WriteLine(hash.Count);
            //return min;




            //拉格朗日四平方和
            if (isSqr(n)) return 1;

            if (isFour(n)) return 4;

            for (int i = 0; i*i < n; i++)
            {
                int j = n - i * i;
                if (isSqr(j)) return 2;
              
            }

            return 3;

        }

        public static bool isSqr(int x)
        {
            int i = (int)Math.Sqrt(x);
            return i * i == x;
        }

        public static bool isFour(int x)
        {
            while (x%4==0) x /= 4;

            return (x - 7) % 8 == 0;
        }

    }
}
